The present invention relates to the field of image compression. More specifically, to the compression of palettized images using an entropy encoder and also using parallel entropy encoder.
Image compression generally operates on digitized images. To digitize an image, the image is sampled at various points in the image, often referred to as pixels. Each pixel has a location within the image and a pixel color. In one example, an image is represented by a two-dimensional array of 1024 by 768 pixels, where each pixel can take on one 24-bit value. Each pixel value can represent a different color, thus allowing the image to be represented using any of 2.sup.24, or 16,777,216, possible colors.
In many applications, each pixel value is associated with a particular color in the image at the time the image is digitized. With this arrangement, the color of a given pixel can be determined by the pixel's value. In other applications, the digital image is a palettized image. In a palettized image, the value of each pixel is not fixed to a color, but is a pointer to an entry in a color palette table. When a palettized imagine is to be displayed, the color of a pixel is found by using the pixel value as an index into the color palette table which maintains the relationship between each pixel value and the color assigned to that pixel value.
A palettization is a selection of a few colors from the set of all possible colors, e.g., 256 (2.sup.8) out of 16,777,216 (2.sup.24) colors, and a method for substituting an arbitrary color by one from the selected few colors. As a result, a palettized image can be efficiently stored as a code book listing (continuing the above example), for each of 256 indices, the full 24-bit color description of the selected colors, followed by the 8-bit index of each pixel in the image. Thus, a space savings occurs by fully describing the selected colors only once and referring to each pixel by just an index into the code book.
Image compression is important in many imaging applications because of the amount of data needed to represent an image. In the above example 24.times.1024.times.768, or 18,874,368 bits (2,359,296 bytes) are needed to represent a single uncompressed image, or 8.times.1024.times.768 (6,291,456 bits) in the case of a palettized image. Compression is even more essential with motion video, which requires a continuous stream of images at a high frame rate, such as 30 images per second. Not only does compression save image storage memory, compression also allows efficient transfer of images over limited bandwidth channels. Of course, for applications such as moving images, the images must be able to be decompressed fast enough so that they can be displayed at the frame rate. While the compression can be done in advance, often the application requires real-time decompression. In embodiments where the compression is done in advance, the input to the decompressor is a block of compressed data which can be stored in a memory device and decompressed at any time after the compression.
One measure of how well compression works is the compression ratio. The compression ratio is the ratio of the size of the uncompressed data to the compressed data. Another measure of the quality of compression is how fast data can be compressed and decompressed. In many applications, the speed of compression is not as important as the speed of decompression, because compression need not occur in real-time.
Often, the compression ratio is improved the more the character of the data is known. Normal digital images are generally the result of the quantization of waveforms, hence they preserve many of the characterizations of the original signal, such as the existence of relative continuity of pixel color values. With palettized images, this continuity is usually not present, and cannot be used directly to improve the compression ratio.
With palettized images, the color difference between two pixel values cannot necessarily be inferred from the pixel values, since the pixel values do not represent pixel colors. Instead they only represent indices into the code table, or color palette table, of color values. The problem of compressing palettized images can be generalized as the problem of compressing a sequence of input symbols where each input symbol is a symbol in an M-ary alphabet.
Y. Chin, et al., "Lossy Compression of Palettized Images", ICASSP-93, Vol. V, pp. 325-328, describes an example of lossy compression of palettized images. While lossy compression generally results in better compression ratios, many applications cannot tolerate the distortion which results from glossy compression, and therefore require lossless compression. With lossless compression, a signal is compressed into a compressed signal which can be decompressed to recover the original signal exactly from the compressed signal, thus no distortion is introduced.
From the above it is seen that an improved method and apparatus for compressing and decompressing palettized images is needed.